﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Threading;
using System.Text.RegularExpressions;

namespace LookAHead
{
    class program
    {
        #region declartion

        #region Algo's Num
        public static int AstarNum = 0;
        public static int IdaStarNum = 1;
        public static int LookAHeadNum = 2;
        public static int LDfsNum = 3;
        public static int BfsNum = 4;
        public static int UniformCostSearchNum = 5;
        public static int MrecNum = 6;
        public static int LookAHeadWithBpmxNum = 7;
        public static int MrecWithBpmxNum = 8;
        #endregion Algo's Num
        #region Define
        public static int operators = 8;//the number of operators for this space problem
        public static double stoper = 4; //algo stops after stoper minutes
        public static bool LookaHeadByNextBest = true; //if false then grow k by 1 each itration
        public static bool WithBpmx = false; //detection to know if we are at c\bpmx algo's at the moment
        public static bool Debug = false; //if you want wo debug change it to true for clock not stoping
        public static int Num_algo = 9;//the number of algoritem 
        public static int Num_Lookahead = 10;//the number of difreent AstarLookAheadStar
        public static double jump = 1; //size of step jump in lookahead
        #endregion Define
        #region algo's data info
        public static Stopwatch[,] Stopwatch = new Stopwatch[Num_algo, Num_Lookahead];//array of time for all algoritem
        public static int[,] TotalMem = new int[Num_algo, Num_Lookahead];//array of memory for all algoritem
        public static int[,] TotalExpnded = new int[Num_algo, Num_Lookahead]; //array of Total expanded for all algoritem
        public static int[,] TotalReExpnded = new int[Num_algo, Num_Lookahead];//array of Total reexpanded for all algoritem
        public static int[,] TotalGenrated = new int[Num_algo, Num_Lookahead];//array of Total genrated for all algoritem
        public static int[,] TotalReGenrated = new int[Num_algo, Num_Lookahead];//array of Total regenrated for all algoritem
        public static double[,] TotalSolCost = new double[Num_algo, Num_Lookahead];//array of Total SolCoast for all algoritem
        public static int[,] TotalSolDepth = new int[Num_algo, Num_Lookahead];//array of Total SolDepth for all algoritem
        public static int[,] TotalnumIt = new int[Num_algo, Num_Lookahead];//number of itartion for some algorithem
        public static int[,] TotalMaxStackSize = new int[Num_algo, Num_Lookahead];//number of stack size for some algorithem
        public static long[,] TotalLookaHeadVisited = new long[Num_algo, Num_Lookahead];
        public static int[,] Sol = new int[Num_algo, Num_Lookahead];//array of Total LookAheadVisited for all Lkalgoritem
        #endregion algo's data info
        #region algo's Assistance parm
        public static string[] AlgoNames = { "Astar", "IdaStar", "LookAHead", "Dfs", "Bfs", "UniformCostSearch", "Merc", "LookAHeadWithBpmx", "MrecWithBpmxNum" };
        public static int memory = 0; //size of open list+close list
        public static int memoryMrec = 0; //size of memory from lookahead for use for mrec algo
        public static int ReGenrated = 0; //Cell  that is been genrated not in the first time
        public static int Genrated = 0; //Cell that is been genrated in the first time
        public static int expanded = 0; //Cell that is been expanded in the first time
        public static int Reexpanded = 0; //Cell that is been expanded not in the first time
        public static int SolDepth = 0; //the cost for start to goal
        public static long LookaHeadVisited = 0;//the number of Coordinate the is been genrated during lk algoritem
        public static double SolCost = 0;//will Conatain the cost from start to goal
        public static int CurrentAlgo; //the number of algo that is running at the moment
        public static bool AncestorDetection = false;//check param for not duplicate my ancestors
        public static bool SolFoundInAstarLk = false;//indication if sol Found in Astar or Lk
        public static Stopwatch StopwatchHelp = new Stopwatch();//a Stopwatch helper for some algoritem for time breake
        public static Stack<key> InStack = new Stack<key>();//will conatin the cells in LDFS algoritem
        public static Cell ans = null;//conatin the goal Cell if found during algoritem
        public static String ansPath = null;//the string path from one point to another
        public static double UB = 9999999999999;//Upper bound
        public static int MaxStackSize = 0;
        public static int numIt = 0;//the number of itartion in ida* and in mrec
        public static bool KeepRuninng = true;//stop running other algo
        public static bool MrecDetection;
        public static Random random = new Random();
        public static Grid GridBoard = null;
        public class key
        {
            public int x; public int y; public int op; public double g; public double f; public int depth;
            public key(int _x, int _y, int _op) { x = _x; y = _y; op = _op; }
            public key(int _x, int _y, int _op, double _g, double _f, int _depth) { x = _x; y = _y; op = _op; g = _g; f = _f; depth = _depth; }
        }
        #endregion algo's Assistance parm

        #endregion declartion
        static void Main(string[] args)
        {
            #region WHAT DO YOU WANT TO DO???
            //Debug = true; // if you want to debug
            #region RunFile
            /*Run Existing File And See Resoults
            FileRW.ReadAndRunBoard(String InputFile, String MbhInputFile,String OutputFile);
            FileRW.ReadAndRunBoard(String InputFile, String OutputFile);
            */
            #endregion RunFile
            #region AtccheFiles
            //FileRW.AttachFiles(); //Atcche all output files to one file
            #endregion AtccheFiles
            #region CreateNewFile
            //CreateBoard(int size, int obsitcle,String FileToPrint);
            #endregion CreateNewFile
            #region CreateMbhFile
            //FileRW.CreateMbhFile(InputFile, MbhFile);
            #endregion CreateMbhFile
            #endregion WHAT DO YOU WANT TO DO???
            FileRW.AttachFiles();
        }
        #region create
        /********************************************************************************/
        public static void CreateBoard(int size, int obsitcle, String FileToPrint)
        /* Create Grid board in size "size*size" with obstacle  presantcge ,and save the borad to file "FileToPrint"*/
        {
            GridBoard = new Grid(size, size, obsitcle);
            GridBoard.PrintGridToFile(FileToPrint);
        }
        /********************************************************************************/
        public static void CreateAndRunFile(int size, int obstacle, int FileNumber)
        /*create and run the file with this size and amount of absticle , ths FileNumber is just for index and record*/
        {
            String FileNameIn = "input/" + size + "/" + obstacle + "/" + FileNumber + ".txt";
            String FileNameOut = "output/" + size + "/" + obstacle + "/" + FileNumber + ".txt";
            if (!File.Exists(FileNameOut))
            {
                CreateBoard(size, obstacle, FileNameIn);
                FileRW.ReadAndRunBoard(FileNameIn, "", FileNameOut); //run sol for board
            }
        }
        /********************************************************************************/
        public static void CreateAndRunAllFiles()
        // for Grids in sizes {0,10,500,1000} for each size with obsitcle of {0,25,50,75} create a board and run it to soltion if possible
        {
            int[] Size = {10, 500, 1000 };
            int[] Obsitcle = { 0, 25, 50, 75 };
            for (int i = 0; i < Size.Length; i++)
                for (int j = 0; j < Obsitcle.Length; j++)
                    for (int y = 0; y < 100; y++)
                        CreateAndRunFile(Size[i], Obsitcle[j], y);
        }
        #endregion create
        #region Init&EndFunc
        /********************************************************************************/
        public static void RunAlgo(String PdbFile, String FileOut)
        /*run all search algoritem 
        * after each algoritem using function "UpdateDetails(cordinates of algoritem)"
        * after all algoritems print all sol to file "FileOut" using function "Print_Final_Details(FileOut)"*/
        {
            RunAstar();
            if (KeepRuninng)
            {
                RunLdfs(GridBoard.start, TotalSolCost[0, 0]);
                if (KeepRuninng)
                    RunIDAstar();
                KeepRuninng = true;
                for (int j = 0; (j < Num_Lookahead && KeepRuninng); j++)
                    LookaHead_run(GridBoard.start, j);
                KeepRuninng = true;
                for (int j = 0; (j < Num_Lookahead && KeepRuninng); j++)
                    if (Sol[LookAHeadNum, j] == 0)
                        KeepRuninng = false;
                    else
                        RunMrec(j);
                RunBfs();
                RunUniformCostSearch();
            }
            //bpmx
            KeepRuninng = true;
            if (File.Exists(PdbFile))
            {
                program.WithBpmx = true;
                FileRW.ReadAndRunBoardWithMbh(PdbFile);
                RunAstarWithPathMax();
                if (KeepRuninng)
                {
                    RunIDAstarWithBpmx();
                    KeepRuninng = true;
                    for (int j = 0; (j < Num_Lookahead && KeepRuninng); j++)
                        LookaHead_runWithBpmx(GridBoard.start, j);
                    KeepRuninng = true;
                    for (int j = 0; (j < Num_Lookahead && KeepRuninng); j++)
                        if (Sol[LookAHeadWithBpmxNum, j] == 0)
                            KeepRuninng = false;
                        else
                            RunMrecWithBpmx(j);
                }
            }
            FileRW.PrintFinalDetails(FileOut);
        }
        /********************************************************************************/
        public static void Init()
        //init all needed paramers between diffrent boards
        {
            random = new Random();
            KeepRuninng = true;
            LookaHeadVisited = memory = expanded = Genrated = ReGenrated = Reexpanded = SolDepth = 0;
            SolCost = 0;
            Stopwatch = new Stopwatch[Num_algo, Num_Lookahead];
            StopwatchHelp = new Stopwatch();
            InStack = new Stack<key>();
            ans = null;
            ansPath = null;
            WithBpmx = false;
            TotalMem = new int[Num_algo, Num_Lookahead];
            TotalExpnded = new int[Num_algo, Num_Lookahead];
            TotalReExpnded = new int[Num_algo, Num_Lookahead];
            TotalGenrated = new int[Num_algo, Num_Lookahead];
            TotalReGenrated = new int[Num_algo, Num_Lookahead];
            TotalSolCost = new double[Num_algo, Num_Lookahead];
            TotalSolDepth = new int[Num_algo, Num_Lookahead];
            TotalLookaHeadVisited = new long[Num_algo, Num_Lookahead];
            Sol = new int[Num_algo, Num_Lookahead];
            for (int i = 0; i < Num_algo; i++)
                for (int j = 0; j < Num_Lookahead; j++)
                    Stopwatch[i, j] = new Stopwatch();
        }
        /********************************************************************************/
        public static void InitAlgo(int AlgoNum, int k)
        {
            Console.WriteLine("----------------------" + AlgoNames[AlgoNum] + "-------------------");
            CurrentAlgo = AlgoNum;
            StopwatchHelp = new Stopwatch();
            Stopwatch[AlgoNum, k] = new Stopwatch();
            StopwatchHelp.Start();
            Stopwatch[AlgoNum, k].Start();
        }
        /********************************************************************************/
        public static void EndAlgo(int AlgoNum, int k)
        {
            Stopwatch[AlgoNum, k].Stop();
            StopwatchHelp.Stop();
            GridBoard.printPathToSol();
            Console.WriteLine("Time elapsed: {0}", Stopwatch[AlgoNum, k].Elapsed.TotalMilliseconds);
            Console.WriteLine("----------------------" + AlgoNames[AlgoNum] + "-------------------");
            GridBoard.ClearGrid();
            UpdateDetails(AlgoNum, k);
        }
        /********************************************************************************/
        public static void UpdateDetails(int i, int j)
        /* saving important data from algoritem for docimention and reaserch later*/
        {
            if (ans != null)
            {
                TotalMem[i, j] = memory;
                memoryMrec = memory;
                TotalExpnded[i, j] = expanded;
                TotalReExpnded[i, j] = Reexpanded;
                TotalGenrated[i, j] = Genrated;
                TotalReGenrated[i, j] = ReGenrated;
                TotalSolCost[i, j] = SolCost;
                TotalSolDepth[i, j] = SolDepth;
                TotalLookaHeadVisited[i, j] = LookaHeadVisited;
                Sol[i, j] = 1;
            }
            else
            {
                SolDepth = 0;
                SolCost = 0;
                if ((CurrentAlgo == LDfsNum || CurrentAlgo == AstarNum || CurrentAlgo == LookAHeadNum) || (CurrentAlgo == LookAHeadWithBpmxNum) || (CurrentAlgo == MrecNum) || (CurrentAlgo == MrecWithBpmxNum))
                    KeepRuninng = false;
            }
            SolCost = memory = expanded = Genrated = ReGenrated = Reexpanded = SolDepth = 0;
            LookaHeadVisited = 0;
            ans = null;
            ansPath = null;
        }
        /********************************************************************************/
        #endregion Init&EndFunc
        #region algorithm
        #region mrec
        #region Regular
        /********************************************************************************/
        public static void RunMrec(int k)
        {
            memoryMrec = TotalMem[LookAHeadNum, k];
            double threshold = GridBoard.start.g + GridBoard.start.h;
            numIt = 0; MaxStackSize = 0;
            InitAlgo(MrecNum, k);
            InStack = new Stack<key>();
            AncestorDetection = true;
            while (ans == null)
            {
                threshold = Mrec(GridBoard.start, threshold);
                numIt++; //for debug
                if ((threshold == GridBoard.MaxG) || (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug))
                {
                    Console.WriteLine("time stopes");
                    break;
                }
            }
            Console.WriteLine("Num of itrations:" + numIt);
            EndAlgo(MrecNum, k);
            AncestorDetection = false;
            TotalMaxStackSize[MrecNum, k] = MaxStackSize;
            TotalnumIt[MrecNum, k] = numIt;
            MrecDetection = false;
        }
        /********************************************************************************/
        public static double Mrec(Cell start, double threshold)
        {
            MrecDetection = true;
            int StackSize = 0;
            Cell parent, child;
            key k;
            double NewThreshold = GridBoard.MaxG;
            start.ChangeToOpen();
            start.InBranch = true;
            if (start.IsEqual(GridBoard.goal))
            {
                ans = start;
                return NewThreshold;
            }
            start.expand();
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op)); //inserting all start's children to stack + dummy for deleting
            StackSize = StackSize + 8;
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                    return NewThreshold;
                if (memory >= memoryMrec)
                    MrecDetection = false;
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue;
                }
                StackSize--;
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    if (MyMath.Greater(child.g + child.h, threshold))//folding branch back up from the leaf
                        NewThreshold = Math.Min(NewThreshold, child.g + child.h);
                    else
                    {
                        child.ChangeToOpen();
                        if (child.IsEqual(GridBoard.goal))
                        {
                            ans = child;
                            return NewThreshold;
                        }
                        if (MrecDetection)
                            child.MrecRemmber = true;
                        child.expand();
                        child.InBranch = true;
                        for (int op = operators; op >= 0; op--)//inserting all child's children to stack
                            InStack.Push(new key(child.x, child.y, op));
                        StackSize = StackSize + 8;
                    }
                }
                MaxStackSize = Math.Max(MaxStackSize, StackSize);
            }
            return NewThreshold;
        }
        /********************************************************************************/
        #endregion Regular
        #region Bpmx
        public static void RunMrecWithBpmx(int k)
        {
            memoryMrec = TotalMem[LookAHeadWithBpmxNum, k];
            double threshold = GridBoard.start.g + GridBoard.start.h;
            numIt = 0; MaxStackSize = 0;
            InitAlgo(MrecWithBpmxNum, k);
            InStack = new Stack<key>();
            AncestorDetection = true;
            while (ans == null)
            {
                threshold = MrecWithBpmx(GridBoard.start, threshold);
                numIt++; //for debug
                if ((threshold == GridBoard.MaxG) || (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug))
                {
                    Console.WriteLine("time stopes");
                    break;
                }
            }
            Console.WriteLine("Num of itrations:" + numIt);
            EndAlgo(MrecWithBpmxNum, k);
            AncestorDetection = false;
            TotalMaxStackSize[MrecWithBpmxNum, k] = MaxStackSize;
            TotalnumIt[MrecWithBpmxNum, k] = numIt;
            MrecDetection = false;
        }

        /********************************************************************************/
        public static double MrecWithBpmx(Cell start, double threshold)
        {
            MrecDetection = true;
            int StackSize = 0;
            Cell parent, child;
            key k;
            double dist;
            double NewThreshold = GridBoard.MaxG;
            start.ChangeToOpen();
            start.InBranch = true;
            if (start.IsEqual(GridBoard.goal))
            {
                ans = start;
                return NewThreshold;
            }
            start.expand();
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op)); //inserting all start's children to stack + dummy for deleting
            StackSize = StackSize + 8;
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                    return NewThreshold;
                if (memory >= memoryMrec)
                    MrecDetection = false;
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue;
                }
                StackSize--;
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    dist = Math.Abs(child.g - parent.g);
                    if (MyMath.Greater(child.h - parent.h, dist))
                        parent.h = child.h - dist; //bpmx
                    else if (MyMath.Greater(parent.h - child.h, dist))
                        child.h = parent.h - dist; //pathmax
                    if (MyMath.Greater(child.g + child.h, threshold))//folding branch back up from the leaf
                        NewThreshold = Math.Min(NewThreshold, child.g + child.h);
                    else
                    {
                        child.ChangeToOpen();
                        if (child.IsEqual(GridBoard.goal))
                        {
                            ans = child;
                            return NewThreshold;
                        }
                        if (MrecDetection)
                        {
                            //child.fu = child.g + child.h;
                            child.MrecRemmber = true;
                        }
                        child.expand();
                        child.InBranch = true;
                        for (int op = operators; op >= 0; op--)//inserting all child's children to stack
                            InStack.Push(new key(child.x, child.y, op));
                        StackSize = StackSize + 8;
                    }
                }
                MaxStackSize = Math.Max(MaxStackSize, StackSize);
            }
            return NewThreshold;
        }
        #endregion Bpmx
        #endregion mrec
        /********************************************************************************/
        #region Ida*
        #region Regular
        public static void RunIDAstar()
        {
            AncestorDetection = true;
            double threshold = GridBoard.start.g + GridBoard.start.h;
            InStack = new Stack<key>();
            InitAlgo(IdaStarNum, 0);
            while (ans == null)
            {
                threshold = IDAstar(GridBoard.start, threshold);
                numIt++; //for debug
                if ((threshold == GridBoard.MaxG) || (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug))
                {
                    Console.WriteLine("time stopes");
                    break;
                }
            }
            Console.WriteLine("Num of itrations:" + numIt);
            EndAlgo(IdaStarNum, 0);
            AncestorDetection = false;
            TotalMaxStackSize[IdaStarNum, 0] = MaxStackSize;
            TotalnumIt[IdaStarNum, 0] = numIt;
            numIt = 0;
            MaxStackSize = 0;
        }
        /********************************************************************************/
        public static double IDAstar(Cell start, double threshold)
        {
            int StackSize = 0;
            Cell parent, child;
            key k;
            double NewThreshold = GridBoard.MaxG;
            start.ChangeToOpen();
            start.InBranch = true;
            if (start.IsEqual(GridBoard.goal))
            {
                ans = start;
                return NewThreshold;
            }
            start.expand();
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op)); //inserting all start's children to stack + dummy for deleting
            StackSize = StackSize + 8;
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                    return NewThreshold;
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue;
                }
                StackSize--;
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    if (MyMath.Greater(child.g + child.h, threshold))
                        NewThreshold = Math.Min(NewThreshold, child.g + child.h);
                    //folding branch back up from the leaf
                    else
                    {
                        child.ChangeToOpen();
                        if (child.IsEqual(GridBoard.goal))
                        {
                            ans = child;
                            return NewThreshold;
                        }
                        child.expand();
                        child.InBranch = true;
                        for (int op = operators; op >= 0; op--)//inserting all child's children to stack
                            InStack.Push(new key(child.x, child.y, op));
                        StackSize = StackSize + 8;
                        continue;
                    }

                }
                MaxStackSize = Math.Max(MaxStackSize, StackSize);
            }
            return NewThreshold;
        }
        /********************************************************************************/
        #endregion Regular
        #region Bpmx
        public static void RunIDAstarWithBpmx()
        {
            AncestorDetection = true;
            double threshold = GridBoard.start.g + GridBoard.start.h;
            InStack = new Stack<key>();
            InitAlgo(IdaStarNum, 1);
            while (ans == null)
            {
                threshold = IDAstarWithBpmx(GridBoard.start, threshold);
                numIt++; //for debug
                if ((threshold == GridBoard.MaxG) || (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug))
                {
                    Console.WriteLine("time stopes");
                    break;
                }
            }
            Console.WriteLine("Num of itrations:" + numIt);
            EndAlgo(IdaStarNum, 1);
            AncestorDetection = false;
            TotalMaxStackSize[IdaStarNum, 1] = MaxStackSize;
            TotalnumIt[IdaStarNum, 1] = numIt;
            numIt = 0;
            MaxStackSize = 0;
        }
        /********************************************************************************/
        public static double IDAstarWithBpmx(Cell start, double threshold)
        {
            int StackSize = 0;
            Cell parent, child;
            key k;
            double dist;
            double NewThreshold = GridBoard.MaxG;
            start.ChangeToOpen();
            start.InBranch = true;
            if (start.IsEqual(GridBoard.goal))
            {
                ans = start;
                return NewThreshold;
            }
            start.expand();
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op)); //inserting all start's children to stack + dummy for deleting
            StackSize = StackSize + 8;
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                    return NewThreshold;
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue;
                }
                StackSize--;
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    dist = Math.Abs(child.g - parent.g);
                    if (MyMath.Greater(child.h - parent.h, dist))
                        parent.h = child.h - dist; //bpmx
                    else if (MyMath.Greater(parent.h - child.h, dist))
                        child.h = parent.h - dist; //pathmax
                    if (MyMath.Greater(child.g + child.h, threshold))
                        NewThreshold = Math.Min(NewThreshold, child.g + child.h);
                    //folding branch back up from the leaf
                    else
                    {
                        child.ChangeToOpen();
                        if (child.IsEqual(GridBoard.goal))
                        {
                            ans = child;
                            return NewThreshold;
                        }
                        child.expand();
                        child.InBranch = true;
                        for (int op = operators; op >= 0; op--)//inserting all child's children to stack
                            InStack.Push(new key(child.x, child.y, op));
                        StackSize = StackSize + 8;
                        continue;
                    }

                }
                MaxStackSize = Math.Max(MaxStackSize, StackSize);
            }
            return NewThreshold;
        }
        #endregion Bpmx
        #endregion Ida*
        /********************************************************************************/
        #region BFS
        public static void RunBfs()
        {
            InitAlgo(BfsNum, 0);
            Bfs();
            EndAlgo(BfsNum, 0);
        }
        /********************************************************************************/
        public static void Bfs()
        {
            Queue<Cell> BQ = new Queue<Cell>();
            BQ.Enqueue(GridBoard.start);
            GridBoard.start.ChangeToOpen();
            Cell father, child;
            while ((BQ.Count > 0) && (ans == null))
            {
                father = BQ.Dequeue();
                if (father.IsEqual(GridBoard.goal))
                {
                    ans = father;
                    return;
                }
                father.expand();
                for (int op = 0; op < operators; op++)
                {
                    child = GridBoard.GetChild(father, op);
                    if (child != null)
                        if (child.hash_s == Cell.status.none)
                        { //only intrested node if i meet him in the first time
                            child.ChangeToOpen();
                            BQ.Enqueue(child);
                        }
                }
            }
        }
        #endregion BFS
        /********************************************************************************/
        #region UniformCostSearch
        public static void RunUniformCostSearch()
        {
            InitAlgo(UniformCostSearchNum, 0);
            ans = Astar();
            EndAlgo(UniformCostSearchNum, 0);
        }
        #endregion UniformCostSearch
        /********************************************************************************/
        #region Astar
        #region regular
        /********************************************************************************/
        public static void RunAstar()
        {
            InitAlgo(AstarNum, 0);
            ans = Astar();
            EndAlgo(AstarNum, 0);
        }
        /********************************************************************************/
        public static Cell Astar()
        {
            BinaryHeap OpenHeap = new BinaryHeap();
            Cell min, child;
            OpenHeap.Add(GridBoard.start);
            double f;
            while (OpenHeap.Count > 0)
            {
                min = OpenHeap.Remove();
                if (min.IsEqual(GridBoard.goal))
                    return min;
                min.expand();
                for (int op = 0; op < operators; op++)
                {
                    child = GridBoard.GetChild(min, op);
                    if (child != null)
                    {
                        f = child.h + child.g;
                        if (child.hash_s != Cell.status.open) // if it was open the reorder is otomatic
                            OpenHeap.Add(child);
                        else // if it was open the reorder is otomatic
                            OpenHeap.ReOrder(child);
                    }
                }
            }
            return null;
        }
        /********************************************************************************/
        #endregion regular
        #region PathMax
        public static void RunAstarWithPathMax()
        {
            InitAlgo(AstarNum, 1);
            ans = AstarWithPathMax();
            EndAlgo(AstarNum, 1);
        }
        /********************************************************************************/
        public static Cell AstarWithPathMax()
        {
            BinaryHeap OpenHeap = new BinaryHeap();
            Cell min, child;
            double dist;
            OpenHeap.Add(GridBoard.start);
            double f;
            while (OpenHeap.Count > 0)
            {
                min = OpenHeap.Remove();
                if (min.IsEqual(GridBoard.goal))
                    return min;
                min.expand();
                for (int op = 0; op < operators; op++)
                {
                    child = GridBoard.GetChild(min, op);
                    if (child != null)
                    {
                        dist = Math.Abs(child.h - min.h);
                        if (MyMath.Greater(min.h - child.h, dist))
                            child.h = min.h - dist; //pathmax
                        f = child.h + child.g;
                        if (child.hash_s != Cell.status.open)
                            OpenHeap.Add(child);
                        else
                            OpenHeap.ReOrder(child);
                    }
                }
            }
            return null;
        }
        #endregion PathMax
        #endregion Astar

        /********************************************************************************/
        #region LDFS
        public static void RunLdfs(Cell start, double LimitCost)
        {
            AncestorDetection = true;
            MaxStackSize = 0;
            InStack = new Stack<key>();
            InitAlgo(LDfsNum, 0);
            IDAstar(GridBoard.start, LimitCost);
            EndAlgo(LDfsNum, 0);
            AncestorDetection = false;
            TotalMaxStackSize[LDfsNum, 0] = MaxStackSize;
            MaxStackSize = 0;
            numIt = 0;
        }
        #endregion LDFS
        /********************************************************************************/
        #region LookaHead
        #region Bpmx
        public static void LookaHead_runWithBpmx(Cell start, int k)
        {
            UB = GridBoard.MaxG;
            InitAlgo(LookAHeadWithBpmxNum, k);
            AstarLookaHeadWithPathMax(start, k);
            EndAlgo(LookAHeadWithBpmxNum, k);
        }
        /********************************************************************************/
        public static void AstarLookaHeadWithPathMax(Cell start, int k)
        {
            BinaryHeap OpenHeap = new BinaryHeap();
            double NextBest;
            start.ChangeToOpen();
            OpenHeap.Add(start);
            Cell min;
            Cell child;
            double f, LHB, MinCost, dist;
            SolFoundInAstarLk = false;
            while (OpenHeap.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug)
                { ans = null; return; } //time braker
                min = OpenHeap.Remove();
                f = min.g + min.h;
                if (MyMath.GreaterOrEqual(min.fu, UB))
                    return; //halt
                min.expand();
                for (int op = 0; op < operators; op++)
                {
                    child = GridBoard.GetChild(min, op);
                    if (child != null)
                    {
                        dist = min.h - child.h;
                        if (MyMath.Greater(min.h - child.h, dist))
                            child.h = min.h - dist; //pathmax
                        f = child.g + child.h;
                        child.fu = f;
                        if (MyMath.GreaterOrEqual(child.fu, UB))//if (child.fu >= UB)
                            continue; //pruning becouse i found a better way already
                        if (child.IsEqual(GridBoard.goal))
                        {
                            SolFoundInAstarLk = true;
                            ans = child;
                            UB = child.fu;
                        }
                        if ((LookaHeadByNextBest) && (OpenHeap.GetFirst() != null))
                        {
                            NextBest = OpenHeap.GetFirst().fu;
                            LHB = Math.Min(UB, Math.Min(NextBest, min.g + min.h + k * jump));
                        }
                        else
                            LHB = Math.Min(UB, min.g + min.h + k * jump);
                        if (MyMath.LessOrEqual(child.fu, LHB))
                        {// if (child.fu <= LHB)
                            AncestorDetection = true;
                            MinCost = LookaHeadWithBpmx(child, LHB);
                            if (MyMath.Greater(MinCost, f))//if (MinCost > f)
                                child.fu = MinCost;
                            AncestorDetection = false;
                        }
                        if (child.hash_s == Cell.status.open)//reorder
                            OpenHeap.ReOrder(child);
                        else//entering to openlist
                            OpenHeap.Add(child);
                    }
                }
            }
            return;
        }
        /********************************************************************************/
        public static void InsertToBranch(Cell start)
        //inserting all starts' ancestor's to branch
        {
            Cell c = start;
            while (c != null)
            {
                c.InBranch = true;
                c = c.parent;
            }
        }
        /********************************************************************************/
        public static void ExitFromBranch(Cell start)
        //exiting all starts' ancestor's to branch
        {
            Cell c = start;
            while (c != null)
            {
                c.InBranch = false;
                c = c.parent;
            }
        }
        /********************************************************************************/
        public static double LookaHeadWithBpmx(Cell start, double LHB)
        {
            double MinCost = GridBoard.MaxG;
            InsertToBranch(start);
            double f_child, g_child, h_child, h_parent = 0;
            Cell child, parent;
            double dist;
            key k;
            InStack = new Stack<key>();
            start.HInBranch = start.h;
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op, start.g, start.g + start.h, start.GetDepth())); //inserting all start's children to stack + dummy chiled
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                { ans = null; return MinCost; }
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue; //going back to while
                }
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    dist = child.GetDistance(parent);
                    g_child = k.g + dist;
                    h_child = child.CalcHFromMBH(program.GridBoard.goal);
                    if (MyMath.Greater(h_child - parent.HInBranch, dist))
                        parent.HInBranch = child.h - dist; //bpmx
                    else if (MyMath.Greater(parent.HInBranch - h_child, dist))
                        h_child = parent.HInBranch - dist; //pathmax
                    f_child = g_child + h_child;
                    if (child.IsEqual(GridBoard.goal))
                    {
                        if (MyMath.Less(f_child, UB))
                        {//if (f_child < UB) /**/
                            ans = child;
                            UB = f_child;
                            MinCost = Math.Min(MinCost, f_child);
                            SolDepth = k.depth + 1;
                            SolCost = g_child;
                            SolFoundInAstarLk = false;
                        }
                    }
                    else
                    {
                        if (MyMath.Greater(f_child, LHB))//if (f_child > LHB)
                            MinCost = Math.Min(MinCost, f_child);
                        else
                            if (MyMath.GreaterOrEqual(f_child, UB))//if (f_child >= UB)
                                MinCost = Math.Min(MinCost, f_child);
                            else
                            {
                                child.InBranch = true;
                                child.HInBranch = h_child;
                                for (int op = operators; op >= 0; op--)
                                    InStack.Push(new key(child.x, child.y, op, g_child, f_child, k.depth + 1)); //inserting all start's children to stack + dummy chiled
                            }

                    }
                }
            }
            ExitFromBranch(start);
            return MinCost;
        }
        /********************************************************************************/
        #endregion Bpmx
        #region Regular
        public static void LookaHead_run(Cell start, int k)
        {
            UB = GridBoard.MaxG;
            InitAlgo(LookAHeadNum, k);
            AstarLookaHead(start, k);
            EndAlgo(LookAHeadNum, k);
        }
        /********************************************************************************/

        public static void AstarLookaHead(Cell start, double k)
        {
            BinaryHeap OpenHeap = new BinaryHeap();
            double NextBest = -1;
            start.ChangeToOpen();
            OpenHeap.Add(start);
            Cell min;
            Cell child;
            double f, LHB, MinCost;
            SolFoundInAstarLk = false;
            while (OpenHeap.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug)
                { ans = null; return; } //time braker
                min = OpenHeap.Remove();
                f = min.g + min.h;
                if (MyMath.GreaterOrEqual(min.fu, UB))
                    return; //halt
                min.expand();
                for (int op = 0; op < operators; op++)
                {
                    child = GridBoard.GetChild(min, op);
                    if (child != null)
                    {
                        f = child.g + child.h;
                        child.fu = f;
                        if (MyMath.GreaterOrEqual(child.fu, UB))//if (child.fu >= UB)
                            continue; //pruning becouse i found a better way already
                        if (child.IsEqual(GridBoard.goal))
                        {
                            SolFoundInAstarLk = true;
                            ans = child;
                            UB = child.fu;
                        }
                        if ((LookaHeadByNextBest) && (OpenHeap.GetFirst() != null))
                        {
                            NextBest = OpenHeap.GetFirst().fu;
                            LHB = Math.Min(UB, Math.Min(NextBest, min.g + min.h + k * jump));
                        }
                        else
                            LHB = Math.Min(UB, min.g + min.h + k * jump);
                        if (MyMath.LessOrEqual(child.fu, LHB))
                        {// if (child.fu <= LHB)
                            AncestorDetection = true;
                            MinCost = LookaHead(child, LHB);
                            if (MyMath.Greater(MinCost, f))//if (MinCost > f)
                                child.fu = MinCost;
                            AncestorDetection = false;
                        }
                        if (child.hash_s == Cell.status.open)//reorder
                            OpenHeap.ReOrder(child);
                        else//entering to openlist
                            OpenHeap.Add(child);
                    }

                }
            }
            return;
        }
        /********************************************************************************/
        public static double LookaHead(Cell start, double LHB)
        {
            double MinCost = GridBoard.MaxG;
            InsertToBranch(start);
            double f_child, g_child;
            Cell child, parent;
            double dist;
            key k;
            InStack = new Stack<key>();
            for (int op = operators; op >= 0; op--)
                InStack.Push(new key(start.x, start.y, op, start.g, start.g + start.h, start.GetDepth())); //inserting all start's children to stack + dummy chiled
            while (InStack.Count > 0)
            {
                if (StopwatchHelp.Elapsed.TotalMinutes > stoper && !Debug) //quiting the algo becouse it's taking too long
                { ans = null; return MinCost; }
                k = InStack.Pop();
                parent = GridBoard.Get(k.x, k.y);
                if (k.op == operators)
                {//found dummy - finished with this branch path, now going to my uncle 
                    parent.InBranch = false;
                    continue; //going back to while
                }
                child = GridBoard.GetChild(parent, k.op);
                if (child != null)
                {
                    dist = child.GetDistance(parent);
                    g_child = k.g + dist;
                    f_child = g_child + child.h;
                    if (child.IsEqual(GridBoard.goal))
                    {
                        if (MyMath.Less(f_child, UB))
                        {//if (f_child < UB) /**/
                            ans = child;
                            UB = f_child;
                            MinCost = Math.Min(MinCost, f_child);
                            SolDepth = k.depth + 1;
                            SolCost = g_child;
                            SolFoundInAstarLk = false;
                        }
                    }
                    else
                    {
                        if (MyMath.Greater(f_child, LHB))//if (f_child > LHB)
                            MinCost = Math.Min(MinCost, f_child);
                        else
                            if (MyMath.GreaterOrEqual(f_child, UB))//if (f_child >= UB)
                                MinCost = Math.Min(MinCost, f_child);
                            else
                            {
                                child.InBranch = true;
                                for (int op = operators; op >= 0; op--)
                                    InStack.Push(new key(child.x, child.y, op, g_child, f_child, k.depth + 1)); //inserting all start's children to stack + dummy chiled
                            }

                    }
                }
            }
            ExitFromBranch(start);
            return MinCost;
        }
        #endregion Regular
        #endregion LookaHead
        /********************************************************************************/
        #endregion algorithm
    }
}
